README.md

653. Two Sum IV - Input is a BST

Given a Binary Search Tree and a target number, return true if there exist two elements in the BST such that their sum is equal to the given target.

Example 1:

Input: 5 / \ 3 6 / \ \ 2 4 7 Target = 9 Output: True 

Example 2:

Input: 5 / \ 3 6 / \ \ 2 4 7 Target = 28 Output: False 

Solutions (Python)

1. Set

# Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = NoneclassSolution: deffindTarget(self, root: TreeNode, k: int) ->bool: defhelper(root: TreeNode, k: int, vals: set) ->bool: ifnotroot: returnFalseifk-root.valinvals: returnTruevals.add(root.val) returnhelper(root.left, k, vals) orhelper(root.right, k, vals) returnhelper(root, k, set())

2. Inorder Traversal

# Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = NoneclassSolution: deffindTarget(self, root: TreeNode, k: int) ->bool: nodes= [] curr=rootvals= [] whilenodesorcurr: whilecurr: nodes.append(curr) curr=curr.leftcurr=nodes.pop() vals.append(curr.val) curr=curr.rightl, r=0, len(vals) -1whilel<r: ifvals[l] +vals[r] <k: l+=1elifvals[l] +vals[r] >k: r-=1else: returnTruereturnFalse